/*
    Aufgabe 4) Rekursion mit Strings
*/
public class Aufgabe4 {

    private static String insertCharValue(String text) {
        if (text.length() == 0)
           return "";

        String ownString = "("
                + Integer.toString((int) text.charAt(0))
                + text.charAt(0)
                + ")"
                // recursion step
                + insertCharValue(text.substring(1));
        return ownString;
    }
    
    private static String removeCharsInString(String text) {
        // the first char is deleted automagically
        if (text.length() == 1)
            return "";

        // compare last and first character
        boolean isDuplicate = text.charAt(text.length() - 1) == text.charAt(0);
        // construct TAIL part of string, by judging whether the last char differs from the first
        String ownString = (isDuplicate ? "" : Character.toString(text.charAt(text.length() - 1)));

        // recursive step by returning substring + TAIL part of string
        return removeCharsInString(text.substring(0, text.length() - 1))
                + ownString;
    }

    private static String shiftMaxCharRight(String text) {
        // base case of 1 character
        if (text.length() <= 1)
            return text;

        // base case of 2 characters
        if (text.length() == 2) {
            // form the correct string for base case 2
            String result = ""
                    + (char) Math.min(text.charAt(0), text.charAt(1))
                    + (char) Math.max(text.charAt(0), text.charAt(1));
            //System.out.println("2: " + text + " -> " + result);
            return result;
        }

        // determine a middle character in preparation for string trisection
        int middle = text.length() / 2;

        // perform string trisection
        String left = text.substring(0, middle);
        char mid = text.charAt(middle);
        String right = text.substring(middle + 1);

        // determine the correct result for the left substring
        String leftShifted = shiftMaxCharRight(left);
        char maxLeft = leftShifted.charAt(leftShifted.length() - 1);

        // determine the correct result for the right substring
        String rightShifted = shiftMaxCharRight(right);
        char maxRight = rightShifted.charAt(rightShifted.length() - 1);

        // determine, using previously gathered information, how to correctly reconstruct our trisected string
        // the reconstruction leads to correct ordering, therefore solving the problem

        // the base case is having the max(right) be the biggest character, we
        // assume this to generally be the case
        String reconstructed = left + mid + rightShifted;
        // the middle character is bigger than the max(right) character
        if (maxRight <= mid)
            // reconstruction prioritizes mid
            reconstructed = left + right + mid;
        // the max(left) character is bigger than the max(right) character
        if (maxRight <= maxLeft)
            // reconstruction prioritized max(left)
            reconstructed = leftShifted.substring(0, leftShifted.length() - 1)
                    + mid + right + maxLeft;

        //System.out.println(text + " -> " + reconstructed);
        //System.out.println("l: " + maxLeft + ", m: " + mid + ", r: " + maxRight);

        return reconstructed;
    }
    
    public static void main(String[] args) {
        System.out.println(insertCharValue("hallo"));
        System.out.println(insertCharValue("a!"));
        System.out.println(insertCharValue("Ein Test"));
        System.out.println();

        assert (insertCharValue("hallo").equals("(104h)(97a)(108l)(108l)(111o)"));
        assert (insertCharValue("a!").equals("(97a)(33!)"));
        assert (insertCharValue("Ein Test").equals("(69E)(105i)(110n)(32 )(84T)(101e)(115s)(116t)"));

        System.out.println(removeCharsInString("testtrompete"));
        System.out.println(removeCharsInString("test"));
        System.out.println(removeCharsInString("t"));
        System.out.println(removeCharsInString("angabe"));
        System.out.println();

        assert (removeCharsInString("testtrompete").equals("esrompee"));
        assert (removeCharsInString("test").equals("es"));
        assert (removeCharsInString("t").equals(""));
        assert (removeCharsInString("angabe").equals("ngbe"));

        System.out.println(shiftMaxCharRight("acmbwxdzfjdk"));
        System.out.println(shiftMaxCharRight(""));
        System.out.println(shiftMaxCharRight("za"));
        System.out.println(shiftMaxCharRight("a"));
        System.out.println(shiftMaxCharRight("habcdefg"));
        System.out.println(shiftMaxCharRight("abcdefggfedcba"));

        assert (shiftMaxCharRight("acmbwxdzfjdk").equals("acmbwxdfjdkz"));
        assert (shiftMaxCharRight("").equals(""));
        assert (shiftMaxCharRight("za").equals("az"));
        assert (shiftMaxCharRight("a").equals("a"));
        assert (shiftMaxCharRight("habcdefg").equals("abcdefgh"));
    }
}

/*
    Zusatzfrage 1: Was bedeuted der Begriff der Endrekursion?
        end recursion, also known as tail recursion, means making recursive calls,
        such that the evaluation of the first recursive call does not depend
        on subsequent recursive calls. example:
            return n + func(n - 1);
        is not a tail recursion, evaluation is dependent on further calls
        (all of which are added on the stack in the meanwhile)
            return func(n - 1, n);
        is a tail recursion, as the evaluation is always shifted on the next call
        until a call decides to fully evaluate, all state being encoded in our parameters
    Zusatzfrage 2: Was ist der Unterschied zwischen linearer und verzweigter Rekursion?
        linear recursion grows linearly, meaning growth can be drawn on a line with linear steps:
            f(3) -> f(2) -> f(1) -> f(0)
        linear recursion, where each recursive step spawns only one other call

        "verzweige Rekursion" means recursion with multiple paths, such that each recursive call
        can potentially call itself again more than once in each recursive iteration,
        leading to exponential growth of the call stack:
            search(element) -> search(leftHalf), search(rightHalf)
             -> search(leftleftHalf), search(leftrightHalf), search(rightleftHalf), search(rightrightHalf)
             ...
*/
